package com.example.find;

/**
 * @author zhy
 * @version 1.0.0
 * @ClassName FindSolution.java
 * @Description TODO
 * @createTime 2020年12月15日 09:54:00
 */
public class FindSolution {

    /**
     * 现有一个n*n的二维正整数数组nums，每行元素保证递增，每列元素保证递增，
     * 求某正整数x是否存在于该二维数组中，需要尽量优化时间和空间复杂度；
     * 思路：从右上角开始查找
     *
     * @param nums
     * @param x
     * @return
     */
    public static boolean searchMatrix(int[][] nums, int x) {
        if (null == nums || nums.length == 0 || nums[0].length == 0) {
            return false;
        }
        int rows = nums.length;
        int columns = nums[0].length;
        int row = 0;
        int column = columns - 1;
        while (row < rows && column >= 0) {
            int num = nums[row][column];
            if (num == x) {
                return true;
            } else if (num > x) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }

    /**
     * 链表中倒数第 k 个节点
     * 初始化： 前指针 former 、后指针 latter ，双指针都指向头节点 head。
     * 构建双指针距离： 前指针 former 先向前走 kk 步（结束后，双指针 former 和 latter 间相距 kk 步）。
     * 双指针共同移动： 循环中，双指针 former 和 latter 每轮都向前走一步，直至 former 走过链表 尾节点 时跳出（跳出后， latter 与尾节点距离为 k−1，即 latter 指向倒数第 k 个节点）。
     * 返回值： 返回 latter 即可。
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode first = head, second = head;
        for (int i = 0; i < k; i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        return second;
    }

    class ListNode {

        int val;

        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }


}
